package leetcode.dp;

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * leetCode 300
 * 最长递增子序列
 * 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数
 * 思路：dp 数组定义为：以 nums[i] 为最大值时的最长上升子序列的长度
 * 进阶： 贪心算法

 */
public class Dp300 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        //利用hasNextXXX()判断是否还有下一输入项
        while (sc.hasNext()) {
            //利用nextXXX()方法输出内容
            String str = sc.next();
            List<Integer> input = Arrays.stream(str.split(",")).map(i -> { return Integer.parseInt(i); }).collect(Collectors.toList());
            System.out.println(Arrays.toString(input.toArray()));
            Integer [] nums = input.toArray(new Integer[input.size()]);
            new Dp300().lengthOfLIS(nums);
        }
    }
    //1,3,6,7,9,4,10,5,6
    public int lengthOfLIS(Integer [] nums) {
        if(nums.length == 0) return 0;
        int [] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        // 子串长度为1和为2的初始化
        for(int i = 1; i < nums.length; i++){
            int curVal = nums[i];
            // 找出i前面比i小的
            for(int j = 0 ; j < i;j ++){
                if(nums[j] < curVal){
                    // 如果nums[j] 比 nums[i] 小 ，那么j到i肯定是增了一个，所以是dp[j] + 1，再和dp[i]比较
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        // 最后要全部走一遍，看最大值
        int res = dp[0];
        for (int i = 0; i < nums.length; i++) {
            res = Integer.max(res, dp[i]);
        }
        return res;
    }
}
